数据结构绪论

发表于 | 更新于: | 分类于
字数统计: 943 字

数据结构的基本概念

一 基本结构和概念

  1. 数据
    数据是信息的载体，是描述客观事物属性的数、字符和所有能输入到计算机并被计算机程序识别和处理的符号的集合。
  2. 数据元素
    数据元素是数据的基本单位，一个数据元素由若干个数据项组成，数据项是构成数据元素的最小单位。
  3. 数据对象
    数据对象是具有相同性质的数据元素的聚合。。

  4. 数据类型
    数据类型是一组值的集合和定义在此集合上一组操作的总称。

    • 原子类型：其值不可再分的数据类型
    • 结构类型：其值可以再分解为若干分量的数据类型
    • 抽象数据类型：抽象数据组织和与之相关的操作

  5. 抽象数据类型(ADT)
    抽象数据类型是一个数学模型和定义在该模型上的一组操作。
    抽象数据组成： 

     * 数据对象
 * 数据关系
 * 基本操作集

  6. 数据结构
    结构是指数据之间的相互关系。
    数据结构是指相互之间存在特定关系的数据元素的集合。
    数据结构构成：

     * 逻辑结构
 * 存储结构
 * 数据的运算

2 数据结构的三要素

  1. 数据的逻辑结构
    逻辑结构是指数据之间的逻辑关系。

    数据逻辑结构分类：

    • 线性结构：
      • 一般线性表
      • 受限线性表：
        • 栈和队列
        • 数组
      • 线性表推广：
        • 广义表
    • 非线性结构：
      • 集合
      • 树形结构
      • 图状结构

  2. 数据的存储结构
    数据的存储结构是指数据结构在计算机中的表示(映像)，也称为物理结构。
    　　
    数据存储结构分类：

    • 顺序存储:逻辑上相邻的元素存储在物理位置也相邻的存储单元
    • 链接存储：借助指示元素地址的指针表示元素之间的关系，只能实现顺序存取
    • 索引存储：建立索引表，索引表中每一项称为索引项(存储关键字和物理地址的映射关系)
    • 散列存储：根据元素的关键字直接计算出该元素的物理地址，也称为Hash存储
  3. 数据的运算
    包括数据的定义和实现。

算法和算法评价

一 算法的基本概念

算法是对特定问题求解步骤的一种描述。算法有五个重要特征。

  1. 有穷性：一个算法在执行有穷步后结束，且每一步在有穷时间内完成
  2. 确定性：相同输入只能得出相同结构
  3. 可行性：算法操作可通过基本运算执行有限次来实现
  4. 输入：一个算法有零个或多个输入
  5. 输出：一个算法有一个或多个输出

算法目标：

  1. 正确性
  2. 可读性
  3. 健壮性
  4. 效率和低存储需求

算法效率的度量

  1. 时间复杂度
    一个语句的频度指该语句在算法中被重复执行的次数，算法中所有语句的频度之和为T(n)，T(n)与算法中的基本运算的频率f(n)同数量级。
    算法的时间复杂度记为：


    T(n)=O(f(n))

    常见时间复杂度比较：
    O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

  2. 空间复杂度
    算法的空间复杂度指算法所耗费的存储空间。
    算法的就地工作是指算法所需存储空间为常量。即空间复杂度为O(1)